package leetcode

import kotlinetc.println

//https://leetcode.com/problems/unique-paths-ii/
/**
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?


 */
fun main(args: Array<String>) {


    // [0,0,0,1],
    // [0,1,0,0],
    // [0,0,0,0]
    val obstacleGrid = arrayOf(
            intArrayOf(0),
            intArrayOf(0)
    )
    uniquePathsWithObstacles(obstacleGrid).println()
    uniquePathsWithObstaclesVersion2(obstacleGrid).println()
}

/**
 * //DP
 * [uniquePaths]
 *
 * 改进写法[uniquePathsWithObstaclesVersion2]
 */
fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {

    if (obstacleGrid.isEmpty()) return 0

    val m = obstacleGrid.size
    val n = obstacleGrid[0].size

    val dp = Array(m, { Array(n, { 0 }) })

    //初始化第一列
    var grid = false
    for (i in 0 until m) {
        if (obstacleGrid[i][0] == 1) {
            grid = true
        }
        if (grid)
            dp[i][0] = 0
        else
            dp[i][0] = 1
    }

    for (i in 1 until n) {
        var obstacleIndex = -1

        for (j in 0 until m) {//每列的每一格


            if (obstacleGrid[j][i] == 1) {
                dp[j][i] = 0
                obstacleIndex = j
            } else {
                var pathij = 0
                for (k in obstacleIndex + 1 until j + 1) {//到达当列的每一个格子的所有可能
                    pathij += dp[k][i - 1]
                }
                dp[j][i] = pathij
            }

        }
    }

    return dp[m - 1][n - 1]
}

/**
 * 可以改进上面的写法，节省内存，并不需要保存所有的二维dp，可以使用一维数组迭代更新
 */
fun uniquePathsWithObstaclesVersion2(obstacleGrid: Array<IntArray>): Int {

    if (obstacleGrid.isEmpty()) return 0

    val m = obstacleGrid.size
    val n = obstacleGrid[0].size

    val dp = Array(m, { 0 })


    //初始化第一列
    var grid = false
//    for (i in 0 until m) {
//        if (obstacleGrid[i][0] == 1) {
//            grid = true
//        }
//        if (grid)
//            dp[i] = 0
//        else
//            dp[i] = 1
//    }
    if (obstacleGrid[0][0] == 1)
        dp[0] = 0
    else dp[0] = 1

    for (i in 0 until n) {//列
        for (j in 0 until m) {//每列的每一行
            if (obstacleGrid[j][i] == 1) {
                dp[j] = 0
            } else {
                if (j > 0)
                    dp[j] += dp[j - 1]
//                var pathij = 0
//                for (k in obstacleIndex + 1 until j + 1) {//到达当列的每一个格子的所有可能
//                    pathij += dp[k]
//                }
//                dp[j] = pathij
            }

        }
    }

    return dp[m - 1]
}
